package com.zwj.interview.BFS;


import java.util.Stack;

/**
 * 给定一棵二叉搜索树，请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一
 * <p>
 * 给定如下二叉树：
 * 4
 * 2           6
 * <p>
 * 1    3      5      7
 * <p>
 * 按照中序遍历
 * 1、第一个节点为1，后面的都比1大，那么1就要更新为：1+2+.....+7=28
 * 2、第二个节点为2, 后面的都比2大，那么2就要更新为：2+.....+7=27
 * 3、第三个节点为3，后面的都比3大，那么3就要更新为：3+...+7=25
 * 4、第三个节点为4，后面的都比4大，那么4就要更新为：4+...+7=22
 * 5、第三个节点为5，后面的都比5大，那么5就要更新为：5+...+7=18
 * 6、第三个节点为6，后面的都比6大，那么6就要更新为：6+7=13
 * 7、第三个节点为7，7已经是最后一个节点了，保持不变就行
 */
public class 大于等于当前节点的和替换当前节点 {

    /**
     * 与常规的中序遍历相比，上述代码的不同点在于左右交换。在常规的中序遍历中，
     * 第2个while循环是顺着指向左子节点的指针向下移动的，在上述代码中则是顺着指向右子节点的指针向下移动的。
     * 常规的中序遍历在当前节点出栈遍历之后接着前往它的右子节点，在上述代码中遍历完当前节点后将前往它的左子节点
     *
     * @param root
     * @return 上述代码中的变量sum用来累加遍历过的节点的值。当遍历到一个节点时，值比它大的所有节点都已经遍历过，
     * 因此sum就是所有大于或等于当前节点的值之和，按照题目的规则，用sum替换当前节点的值即可
     */
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int sum = 0;
        while (cur != null || !stack.isEmpty()) {
            /**
             * 对于二叉搜索树而言，要找到大于该节点的所有节点，那么就是向右遍历，然后
             * 将这些值压入栈中
             */
            //将当前节点的右子树压入栈中
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            //从栈中弹出节点，将其值加到sum上重新赋值给cur
            cur = stack.pop();
            sum += cur.val;
            cur.val = sum;
            //然后cur往左走，继续往左走
            cur = cur.left;
        }
        return root;
    }


    //大于等于当前节点的替换节点的值
    public TreeNode convertBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        //要求比当前节点大的节点的和
        int sum = 0;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            //右子树走完了，然后将累加值给到cur
            cur = stack.pop();
            sum += cur.val;
            cur.val = sum;
            cur = cur.left;
        }
        return root;
    }


}
